<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Constraint Behaviours
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial100.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial098.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial102.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc199">14.3</A>&nbsp;&nbsp;Constraint Behaviours</H2><UL>
<LI><A HREF="tutorial101.html#toc100">Consistency Check</A>
<LI><A HREF="tutorial101.html#toc101">Forward Checking</A>
<LI><A HREF="tutorial101.html#toc102">Domain (Arc) Consistency</A>
<LI><A HREF="tutorial101.html#toc103">Bounds Consistency</A>
</UL>

<A NAME="@default362"></A>

As opposed to the theoretical CSP framework sketched in the previous section,
in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> we usually deal with more heterogeneous situation.
We want to allow the integration of very different constraints,
and we want to achieve a separation of constraint propagation and search.
Therefore, we are not interested in an overall problem solving algorithm
which controls search and constraint propagation globally for the whole
problem and all constraints.
We prefer to view the constraint solving process as in figure <A HREF="#figclpexec">14.1</A>:
the search process is controlled by an algorithmic program,
while constraint propagation is performed by data-driven agents which
do local (again algorithmic) computations on one or several constraints.
<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
<DIV CLASS="center">
<IMG SRC="tutorial042.gif">
</DIV>
<BR>
<BR>
<DIV CLASS="center">Figure 14.1: Control during Constraint Solving</DIV><BR>
<BR>

<A NAME="figclpexec"></A>
<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
Individual constraints can then be implemented with different behaviours,
and freely mixed within a single computation.
Constraint behaviours can essentially be characterised by
<A NAME="@default363"></A>
<UL CLASS="itemize"><LI CLASS="li-itemize">
their triggering condition (<B>when</B> are they executed)
<LI CLASS="li-itemize">the action they perform when triggered (<B>what</B> do they do)
</UL>
Let us now look at examples of different constraint behaviours.<BR>
<BR>
<A NAME="toc100"></A>
<H3 CLASS="subsection"><A NAME="htoc200">14.3.1</A>&nbsp;&nbsp;Consistency Check</H3>
<A NAME="@default364"></A>
The <CODE>=&lt;</CODE>/2 predicate, whose standard Prolog version raises an error
when invoked with uninstantiated variable, is also implemented by the
<B>suspend</B> library. Both implementations
have the same declarative meaning, but the <B>suspend</B> version can
be considered to be a proper constraint.
It implements a <B>passive test</B>, i.e.
it simply delays until both arguments are numbers, and then succeeds or fails:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- suspend : (X =&lt; 4).
X = X
There is 1 delayed goal.
Yes (0.00s cpu)

?- suspend : (X =&lt; 4), X = 2.
X = 2
Yes (0.00s cpu)

?- suspend : (X =&lt; 4), X = 5.
No (0.00s cpu)
</PRE></BLOCKQUOTE>
<A NAME="toc101"></A>
<H3 CLASS="subsection"><A NAME="htoc201">14.3.2</A>&nbsp;&nbsp;Forward Checking</H3>
<A NAME="@default365"></A>
Often a constraint can already do useful work before all its arguments
are instantiated. In particular, this is the case when we are working
with domain variables. Consider <B>ic</B>'s disequality constraint <CODE>#\=</CODE> :
Even when only one side is instantiated, it can already remove this value
from the domain of the other (still uninstantiated) side:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- X :: 1 .. 5,
   X #\= 3.
X = X{[1, 2, 4, 5]}
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
If both sides are uninstantiated, the constraint cannot do anything useful.
It therefore waits (delays) until one side becomes instantiated,
but then wakes up and acts as before.
This behaviour is sometimes called forward checking [<A HREF="tutorial133.html#VanHentenryck"><CITE>27</CITE></A>]:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- [X,Y] :: 1 .. 5,
   X #\= Y.        % delays
X = X{1 .. 5}
Y = Y{1 .. 5}
There is 1 delayed goal.
Yes (0.00s cpu)

?- X :: 1 .. 5,
   X #\= Y,         % delays
   Y = 3.           % wakes
X = X{[1, 2, 4, 5]}
Y = 3
Yes (0.01s cpu)
</PRE></BLOCKQUOTE>
<A NAME="toc102"></A>
<H3 CLASS="subsection"><A NAME="htoc202">14.3.3</A>&nbsp;&nbsp;Domain (Arc) Consistency</H3>
<A NAME="@default366"></A>
<A NAME="@default367"></A>
For many constraints, even more eager behaviour is possible.
For example, <B>ic</B>'s inequality constraints performs <B>domain updates</B> as
soon as possible, even when one or both arguments are still variables:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- [X, Y] :: 1 .. 5, X #&lt; Y.
X = X{1 .. 4}
Y = Y{2 .. 5}
There is 1 delayed goal.
Yes (0.00s cpu)

?- [X, Y] :: 1 .. 5, X #&lt; Y, X #&gt; 2.
Y = Y{[4, 5]}
X = X{[3, 4]}
There is 1 delayed goal.
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
Inconsistent values are removed form the domains as soon as possible.
This behaviour corresponds to <B>arc consistency</B> as discussed in
section <A HREF="tutorial100.html#csp">14.2</A>.<BR>
<BR>
<A NAME="toc103"></A>
<H3 CLASS="subsection"><A NAME="htoc203">14.3.4</A>&nbsp;&nbsp;Bounds Consistency</H3>
<A NAME="@default368"></A>
Note however that not all <B>ic</B> constraints maintain full domain
arc consistency. For performance reasons, 
the <CODE>#=</CODE> constraint only maintains bounds consistency, which is
weaker, as illustrated by the following example:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- [X, Y] :: 1 .. 5, X #= Y + 1, X #\= 3.
Y = Y{1 .. 4}
X = X{[2, 4, 5]}
There is 1 delayed goal.
Yes (0.00s cpu)
</PRE></BLOCKQUOTE>
Here, the value 2 for Y was not removed even though it is not arc consistent
(there is no value for X which is compatible with it).<BR>
<BR>
<A NAME="@default369"></A>
It is important to understand that this kind of propagation incompleteness
does not affect correctness: the constraint will simply detect the
inconsistency later, when its arguments have become more instantiated.
In terms of the search tree, this means that a branch will not be pruned
as early as possible, and extra time might be spent searching.<BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>Consistency Checking</B><DD CLASS="dd-description"> 
 wait until all variables instantiated, then check
<DT CLASS="dt-description"><B>Forward Checking</B><DD CLASS="dd-description"> 
 wait until one variable left, then compute consequences
<DT CLASS="dt-description"><B>Domain (Arc) Consistency</B><DD CLASS="dd-description"> 
 wait until a domain changes, then compute consequences for other domains
<DT CLASS="dt-description"><B>Bounds Consistency</B><DD CLASS="dd-description"> 
 wait until a domain bound changes, then compute consequences for other bounds
</DL>

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 14.2: Typical Constraint Behaviours</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<HR>
<A HREF="tutorial100.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial098.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial102.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
